//下一个数。给定一个正整数，找出与其二进制表达式中1的个数相同且大小最接近的那两个数（一个略大，一个略小）。 
//
// 示例 1： 
//
// 
// 输入：num = 2（或者0b10）
// 输出：[4, 1] 或者（[0b100, 0b1]）
// 
//
// 示例 2： 
//
// 
// 输入：num = 1
// 输出：[2, -1]
// 
//
// 提示： 
//
// 
// num 的范围在[1, 2147483647]之间； 
// 如果找不到前一个或者后一个满足条件的正数，那么输出 -1。 
// 
//
// Related Topics 位运算 👍 73 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2025-08-18 10:54:17
 * @description 面试题 05.04.下一个数
 
 */
 
public class ClosedNumberLcci {
    public static void main(String[] args) {
    //测试代码
    ClosedNumberLcci fun = new ClosedNumberLcci();
    Solution solution= fun.new Solution();
        System.out.println(Integer.toBinaryString(67));
        solution.findClosedNumbers(67);
        System.out.println(Integer.toBinaryString(56));
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        /*
        * 实际上是将这个数的
        * 最低位的二进制右边有0的1右移 得到略小
        * 最低位的二进制左边有0的1左移  得到略大
        * 找略大的数：
        找到最右边的01，将其变为10。
        然后将10右边的所有1移到最右边，以确保数尽可能小。
        找略小的数：
        找到最右边的10，将其变为01。
        然后将01右边的所有1移到最左边，以确保数尽可能大。
        * 找略大的数（getNext）：
            计算c0：从右到左，统计连续的1的个数（c1）。
            统计c0：在c1之前，统计连续的0的个数。
            计算p：p = c0 + c1，这是最右边非拖尾的0的位置。
            翻转第p位：将0变为1。
            清除p右边的所有位：将p右边的所有位设为0。
            添加c1 - 1个1：在最低位添加c1 - 1个1，以确保1的个数不变。
        找略小的数（getPrev）：
            计算c0：从右到左，统计连续的0的个数。
            统计c1：在c0之前，统计连续的1的个数。
            计算p：p = c0 + c1，这是最右边非拖尾的1的位置。
            翻转第p位：将1变为0。
            清除p右边的所有位：将p右边的所有位设为0。
            添加c1 + 1个1：在紧邻p的右边添加c1 + 1个1，以确保1的个数不变。
        * */
        public int[] findClosedNumbers(int num) {
            return new int[]{getNext(num), getPrev(num)};
        }

    /**
     * 找到比num大且1的个数相同的最小数
     * @param num 输入的正整数
     * @return 满足条件的数，找不到返回-1
     */
    private int getNext(int num) {
        int x = num;
        // 找到最右边的1，例如：0101000 -> 0001000
        int rightOne = x & -x;

        // 将最右边的1左移一位，例如：0101000 + 0001000 = 0110000
        int nextHigherOneBit = x + rightOne;

        // 计算变化的位，例如：0101000 ^ 0110000 = 0011000
        int rightOnesPattern = x ^ nextHigherOneBit;

        // 标准化：将变化的位右移到最右边
        // 例如：0011000 / 0001000 = 110 (即6)
        // 相当于最终只保留了1的高位
        rightOnesPattern = rightOnesPattern / rightOne;

        // 去掉多余的位，保留需要移动的1的个数
        // 例如：110 >> 2 = 1
        // 然后因为在1的位置变化了两位,这两位会在左半部分，右半部分需要去掉
        // 最终rightOnesPattern 相当于不包含
        rightOnesPattern >>= 2;

        // 合并结果：0110000 | 0000001 = 0110001
        int next = nextHigherOneBit | rightOnesPattern;

        // 确保结果是正数
        return next > 0 ? next : -1;
    }

    /**
     * 找到比num小且1的个数相同的最大的数
     * @param num 输入的正整数
     * @return 满足条件的数，找不到返回-1
     */
    private int getPrev(int num) {
        int x = num;
        int temp = x;
        int c0 = 0; // 统计尾随0的个数
        int c1 = 0; // 统计尾随1的个数

        // 统计尾随1的个数，例如：0010111 -> c1=3
        while ((temp & 1) == 1) {
            c1++;
            temp >>= 1;
        }

        // 如果全是1，无法找到更小的数
        if (temp == 0) return -1;

        // 统计尾随1之前的0的个数，例如：0010111 -> c0=1
        while ((temp & 1) == 0 && temp != 0) {
            c0++;
            temp >>= 1;
        }

        // 计算最右边非拖尾1的位置
        int p = c0 + c1; // 例如：1+3=4

        // 清除p右边的所有位，例如：0010111 & (~0 << 5) = 0010000
        x &= ((~0) << (p + 1));

        // 创建c1+1个1的掩码，例如：(1 << 4)-1 = 1111
        int mask = (1 << (c1 + 1)) - 1;

        // 将掩码移动到正确位置，例如：1111 << (1-1) = 1111
        // 然后与原数合并：0010000 | 0001111 = 0011111
        x |= mask << (c0 - 1);

        return x;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
